//给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。 
//
// 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 
//
// 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 
//
// 示例： 
//
// 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
//输出：7 -> 0 -> 8
//原因：342 + 465 = 807
// 
// Related Topics 链表 数学 
// 👍 4676 👎 0

package leetcode.editor.cn;

import common.bean.ListNode;
import common.util.MyUtil;

/**
 * Java：两数相加
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P2_AddTwoNumbers {
    public static void main(String[] args) {
        Solution solution = new P2_AddTwoNumbers().new Solution();
        ListNode l1 = MyUtil.createNode(2, 4, 3, 6, 6, 6, 6);
        ListNode l2 = MyUtil.createNode(5, 6, 4);
        ListNode listNode = solution.addTwoNumbers(l1, l2);
        MyUtil.printListNode(listNode);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 迭代
     * T: O(max(m,n))
     * S: O(max(m,n))
     */
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // 头节点哨兵
            ListNode l3 = new ListNode(0), temp = l3;
            // 进位标识
            int pre = 0;
            for (ListNode tl1 = l1, tl2 = l2; tl1 != null || tl2 != null; ) {
                int i1 = 0, i2 = 0;
                if (tl1 != null) {
                    i1 = tl1.val;
                    tl1 = tl1.next;
                }
                if (tl2 != null) {
                    i2 = tl2.val;
                    tl2 = tl2.next;
                }
                int sum = i1 + i2 + pre;
                // 更新进位
                pre = sum / 10;

                temp.next = new ListNode(sum % 10);
                temp = temp.next;
            }
            // 还有进位需要添加到链表末尾
            if (pre != 0) {
                temp.next = new ListNode(pre);
            }
            // 结果就是哨兵的下一个节点
            return l3.next;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
